/// @tags: DP
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int constexpr N = 4e4 + 5, INF = 0x3f3f3f3f;

int n;
int a[N], stk[N], l, len[N];
LL f[N], prefix[N], suffix[N];
vector<int> vec[N];

inline int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i], a[i] -= i;
  a[n + 1] = INF;
  for (int i = 1, pos; i <= n + 1; ++i) {
    if (stk[l] <= a[i])
      stk[++l] = a[i], len[i] = l;
    else
      stk[pos = upper_bound(stk + 1, stk + l + 1, a[i]) - stk] = a[i], len[i] = pos;
    vec[len[i]].push_back(i);
  }
  vec[0].push_back(0);
  cout << n - (l - 1) << '\n';
  memset(f, INF, sizeof(f));
  f[0] = 0;
  a[0] = -INF;
  for (int i = 1; i <= n + 1; ++i) {
    for (auto u : vec[len[i] - 1]) {
      if (u > i || a[u] > a[i]) continue;
      prefix[u] = 0;
      for (int j = u + 1; j < i; ++j) prefix[j] = prefix[j - 1] + abs(a[j] - a[u]);
      suffix[i] = 0;
      for (int j = i - 1; j > u; --j) suffix[j] = suffix[j + 1] + abs(a[j] - a[i]);
      for (int j = u; j < i; ++j) f[i] = min(f[i], f[u] + prefix[j] + suffix[j + 1]);
    }
  }
  cout << f[n + 1];
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2501 [HAOI2006] 数字序列.in", "r", stdin);
  freopen("P2501 [HAOI2006] 数字序列.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
